Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning

摘要

We present a sampling-based framework for multi-robot motion planning whichcombines an implicit representation of a roadmap with a novel approach forpathfinding in geometrically embedded graphs tailored for our setting. Ourpathfinding algorithm, discrete-RRT (dRRT), is an adaptation of the celebratedRRT algorithm for the discrete case of a graph, and it enables a rapidexploration of the high-dimensional configuration space by carefully walkingthrough an implicit representation of a tensor product of roadmaps for theindividual robots. We demonstrate our approach experimentally on scenarios ofup to 60 degrees of freedom where our algorithm is faster by a factor of atleast ten when compared to existing algorithms that we are aware of.